package tree.从前序与中序遍历序列构造二叉树;


import java.util.HashMap;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //先序：根-左-右 中序： 左-根-右
        /**
         * [3,9,20,15,7] [9,3,15,20,7]
         * [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
         * [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
         * 且无论是先序还是前序，左子树和右子数的数量都是一致的
         * [3,[9],[20,15,7]] [[9],3,[15,20,7]]
         * [9] [9]
         * [[20],[15],[7]] [[15],[20],[7]]
         *  先序遍历可以确定根节点，中序遍历确定左右子树的个数
         *  当左子树长度 或者右子树长度 <= 1 的时候是递归出去的条件
         *
         */
        Map<Integer, Integer> indexMap = new HashMap<>();
        int i = 0;
        for (int in : inorder) {
            indexMap.put(in, i++);
        }
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, preorder.length - 1, indexMap);

    }

    public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> indexMap) {
        if (preStart > preEnd && inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);
        TreeNode leftNode = buildTree(preorder, preStart + 1, preStart + indexMap.get(preorder[preStart]) - inStart, inorder, inStart, indexMap.get(preorder[preStart]) - 1, indexMap);
        TreeNode rightNode = buildTree(preorder, preStart + 1 + indexMap.get(preorder[preStart]) - inStart, preStart + inEnd - indexMap.get(preorder[preStart]), inorder, indexMap.get(preorder[preStart]) + 1, inEnd, indexMap);
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode treeNode = solution.buildTree(new int[]{3, 9,20,15,7}, new int[]{9, 3,15,20,7});
        System.out.println(treeNode);
    }


}
